GATE CSE 2013
Q1.
Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of n nodes?Q2.
The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the postorder traversal sequence of the same tree?Q3.
Consider the following function: int unknown(int n){ int i, j, k=0; for (i=n/2; i<=n; i++) for (j=2; j<=n; j=j*2) k = k + n/2; return (k); } The return value of the function isQ4.
In a k-way set associative cache, the cache is divided into v sets, each of which consists of k lines. The lines of a set are placed in sequence one after another. The lines in set s are sequenced before the lines in set (s+1). The main memory blocks are numbered 0 onwards. The main memory block numbered j must be mapped to any one of the cache lines fromQ6.
Consider the following languages. L_{1}=\{0^{p}1^{q}0^{r}|p,q,r\geq 0\} L_{2}=\{0^{p}1^{q}0^{r} | p,q,r \geq 0, p \neq r \} Which one of the following statements is FALSE?Q7.
A scheduling algorithm assigns priority proportional to the waiting time of a process. Every process starts with priority zero (the lowest priority). The scheduler re-evaluates the process priorities every T time units and decides the next process to schedule. Which one of the following is TRUE if the processes have no I/O operations and all arrive at time zero?Q8.
Which one of the following expressions does NOT represent exclusive NOR of x and y?Q9.
Which of the following statements is/are TRUE for undirected graphs? P: Number of odd degree vertices is even. Q: Sum of degrees of all vertices is even.Q10.
Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is 1/2. What is the expected number of unordered cycles of length three?